package 模拟题.迷宫;

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * 这里要求字典序最小，我们按照DLRU的顺序进行BFS即可。
 */
public class Main {
    //定义四个方向
    public static int[][] dirs = {
            {1, 0},  //下
            {0, -1}, //左
            {0, 1},  //右
            {-1, 0}  //上
    };
    public static boolean[][] visited = new boolean[30][50];
    public static char[] path={'D','L','R','U'};

    public static void main(String[] args) throws IOException {
        String str = "01010101001011001001010110010110100100001000101010\n" +
                "00001000100000101010010000100000001001100110100101\n" +
                "01111011010010001000001101001011100011000000010000\n" +
                "01000000001010100011010000101000001010101011001011\n" +
                "00011111000000101000010010100010100000101100000000\n" +
                "11001000110101000010101100011010011010101011110111\n" +
                "00011011010101001001001010000001000101001110000000\n" +
                "10100000101000100110101010111110011000010000111010\n" +
                "00111000001010100001100010000001000101001100001001\n" +
                "11000110100001110010001001010101010101010001101000\n" +
                "00010000100100000101001010101110100010101010000101\n" +
                "11100100101001001000010000010101010100100100010100\n" +
                "00000010000000101011001111010001100000101010100011\n" +
                "10101010011100001000011000010110011110110100001000\n" +
                "10101010100001101010100101000010100000111011101001\n" +
                "10000000101100010000101100101101001011100000000100\n" +
                "10101001000000010100100001000100000100011110101001\n" +
                "00101001010101101001010100011010101101110000110101\n" +
                "11001010000100001100000010100101000001000111000010\n" +
                "00001000110000110101101000000100101001001000011101\n" +
                "10100101000101000000001110110010110101101010100001\n" +
                "00101000010000110101010000100010001001000100010101\n" +
                "10100001000110010001000010101001010101011111010010\n" +
                "00000100101000000110010100101001000001000000000010\n" +
                "11010000001001110111001001000011101001011011101000\n" +
                "00000110100010001000100000001000011101000000110011\n" +
                "10101000101000100010001111100010101001010000001000\n" +
                "10000010100101001010110000000100101010001011101000\n" +
                "00111100001000010000000110111000000001000000001011\n" +
                "10000001100111010111010001000110111010101101111000";
        char[][] chars = new char[30][50];
        String[] split = str.split("\\n");
        for (int i = 0; i < split.length; i++) {
            chars[i] = split[i].toCharArray();
        }
        bfs(chars);
    }

    public static void bfs(char[][] chars) {
        LinkedList<Point> queue = new LinkedList<>();
        String s = "";
        Point point = new Point(0, 0, s);
        queue.offer(point);
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            Point poll = queue.poll();
            int x = poll.x;
            int y = poll.y;
            String str = poll.str;
            if (x == 29 && y == 49) {   //判断是否到达终点
                System.out.println(str);
                break;
            }
            //按照DLRU的方向扩展可以实现字典序最小
            for (int i = 0; i < dirs.length; i++) {
                int tx = x + dirs[i][0];
                int ty = y + dirs[i][1];
                //判断是否越界
                if (tx < 0 || tx > 29 || ty < 0 || ty > 49) {
                    continue;
                }
                if (chars[tx][ty]=='0'&&!visited[tx][ty]) {  //检查扩展的节点是否已经被访问过并且可以通行
                    queue.offer(new Point(tx, ty, str+path[i]));
                    visited[tx][ty] = true;
                }
            }
        }
    }

}

class Point {
    int x;
    int y;
    String str;

    public Point(int x, int y, String str) {
        this.x = x;
        this.y = y;
        this.str = str;
    }
}